package n001;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class _0827_MakingLargeIsland {

    public static void main(String[] args) {
        _0827_MakingLargeIsland makingLargeIsland = new _0827_MakingLargeIsland();
        int[][] grid = {
                {0,0,0,0,0,0,0},
                {0,1,1,1,1,0,0},
                {0,1,0,0,1,0,0},
                {1,0,1,0,1,0,0},
                {0,1,0,0,1,0,0},
                {0,1,0,0,1,0,0},
                {0,1,1,1,1,0,0}
        };
        System.out.println(makingLargeIsland.largestIsland(grid));
    }

    public int largestIsland(int[][] grid) {
        int rowLen = grid.length;
        int colLen = grid[0].length;

        int islandCount = 2;
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j, islandCount);
                    ++islandCount;
                }
            }
        }

        Map<Integer, Integer> islandAeraMap = new HashMap<>(islandCount);
        islandAeraMap.put(0, 1);
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                int sign = grid[i][j];
                if (sign == 0) {
                    continue;
                }
                if (islandAeraMap.containsKey(sign)) {
                    islandAeraMap.put(sign, islandAeraMap.get(sign) + 1);
                } else {
                    islandAeraMap.put(sign, 1);
                }
            }
        }

        int maxArea = islandAeraMap.values().stream().max(Integer::compareTo).get();
        for (int i = 0; i < rowLen; i++) {
            for (int j = 0; j < colLen; j++) {
                if (grid[i][j] != 0) {
                    continue;
                }
                int area = 0;
                Set<Integer> visited = visit(grid, i, j);
                for (Integer island : visited) {
                    area += islandAeraMap.get(island);
                }
                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }

    public Set<Integer> visit(int[][] grid, int row, int col) {
        Set<Integer> islands = new HashSet<>();
        // 防止周围都不是 0 的情况下，填充的面积不被计入
        islands.add(0);

        int left = 0;
        int right = 0;
        int up = 0;
        int down = 0;

        if (row > 0) {
            up = grid[row - 1][col];
        }
        if (row < grid.length - 1) {
            down = grid[row + 1][col];
        }
        if (col > 0) {
            left = grid[row][col - 1];
        }
        if (col < grid[0].length - 1) {
            right = grid[row][col + 1];
        }

        islands.add(left);
        islands.add(right);
        islands.add(up);
        islands.add(down);
        return islands;
    }

    public void dfs(int[][] grid, int row, int col, int islandSign) {
        if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != 1) {
            return;
        }
        grid[row][col] = islandSign;
        dfs(grid, row - 1, col, islandSign);
        dfs(grid, row + 1, col, islandSign);
        dfs(grid, row, col - 1, islandSign);
        dfs(grid, row, col + 1, islandSign);

    }

}
